This invention relates to digital data storage and retrieval, and more particularly to block-oriented storing of compressed or uncompressed data in randomly-accessed locations of fixed size in a partitioned storage device.
Data compression encoding algorithms are commonly applied to data which is to be archived or stored at the tertiary storage level. In a hierarchy of data storage, a RAM directly accessed by a CPU is often referred to a the primary level, the hard disk as the secondary level, and tape (back up) as the tertiary level. The characteristic of tertiary level storage as commonly implemented which supports use of compression is that the data access is largely sequential. Data is stored in variable-length units, sequentially, without boundaries or constraints on the number of bytes or words in a storage unit. Thus, if a file or page being stored compresses to some arbitrary number of bytes this can be stored as such, without unused memory due to fixed sizes of storage units. Compression can be easily applied in any such case where the data is not randomly accessed but instead is sequentially accessed. For this reason, data compression works well for data streaming devices such as magnetic tape. It has been applied to databases holding very large records on magnetic and optical disks.
Data compression is not readily adaptable for use with random access storage devices such as hard disks or solid-state disks, although in many cases it would be desirable to do so. The reason for this lack of use of data compression is that algorithms for data compression produce compressed data units which are of variable size. Blocks of data of fixed size compress to differing sizes depending upon the patterns of characters in the blocks; data with large numbers of repeating patterns compress to a greater degree than a more random distribution of characters. Text files and spreadsheet files compress to smaller units than executable code or graphics files. This problem of variable-length records has made random access of compressed data records, as managed by operating systems and controllers in computer systems, impractical.
It is the principal object of this invention to provide an improved method of storing data in a computer system or the like, and particularly to provide a method of compressing data blocks for storage in a storage medium having an access capability for storing data units of fixed size. Another objects is to provide an improved data compression arrangement using a random-access type of storage device, where the data units to be stored and recalled are of fixed length and the storage device is accessed in fixed-length increments. A further object is to reduce the amount of unused storage space in a storage device when compressed data units are stored, and therefore increase the storage density. An additional object is to provide an improvement in the cost per byte of storage capacity in a storage device.